1433F - Zero Remainder Sum - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(A) A.rbegin(),A.rend()
#define pb push_back
#define f first
#define s second 
#define dbg(x) do {cerr << #x <<" = " << (x) << endl; } while (false)
//#define dbg(x) do {} while (false)
#define raya do {cerr << "===========================" << endl; } while (false)
//#define raya do {} while (false)
#define bpc __builtin_popcountll//numero de bits para long long
#define bclz __builtin_clzll//leading zeros para ll 
#define max_bit(A) 31-__builtin_clz(A)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> ii; 
const int maxn = 70;
const int inf = 1e9;
int boar[maxn][maxn];
int n,m,k;

vector<int>gen(vector<int> x){
	int dp[maxn][maxn];
	for(int i=0;i<maxn;i++)
		for(int j=0;j<maxn;j++)
			dp[i][j] = -inf;
	dp[0][0] = 0; //take-resto

	for(int pos=0;pos<m;pos++){
		for(int tk=min(pos+1,m/2);tk>0;tk--){
			for(int d=0;d<k;d++){
				dp[tk][(d+x[pos])%k] = max(dp[tk][(d+x[pos])%k] , dp[tk-1][d]+x[pos]);
			}
		}
	}
	vector<int>ret(k,-inf);
	for(int d=0;d<k;d++)
		for(int tk=0;tk<=m/2;tk++)
			ret[d] = max(ret[d] , dp[tk][d]) ;
	return ret;
}
vector<int>merge(vector<int> x,vector<int>y){
	vector<int>ret(k,-inf);
	for(int i=0;i<k;i++){
		for(int j=0;j<k;j++){
			ret[(i+j)%k] = max(ret[(i+j)%k] , x[i]+y[j]);
		}
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	vector<vector<int>> v(n,vector<int>(m));
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>v[i][j];

	vector<int>lst(k,-inf);
	lst[0] = 0 ;
	for(int i=0;i<n;i++){
		lst = merge(lst,gen(v[i]));
	}
	cout<<lst[0]<<endl;
    return 0;
}